package com.berry.oss.erasure;

import java.util.ArrayList;
import java.util.List;

/**
 * 8-bit Galois Field
 * 8 位 伽罗华域
 * <p>
 * This class implements multiplication, division, addition,
 * subtraction, and exponentiation.
 * 这个类实现乘法，除法，加法，减法,求幂
 * <p>
 * The multiplication operation is in the inner loop of
 * erasure coding, so it's been optimized.  Having the
 * class be "final" helps a little, and having the EXP_TABLE
 * repeat the data, so there's no need to bound the sum
 * of two logarithms to 255 helps a lot.
 * 擦除编码的乘法操作在内循环，因此得到了优化，将类定义为 final 可能有点帮助，并且有 EXP_TABLE 重复这些数据，
 * 所以没有必要限制两个对数的和不大于 255 很有用
 */
public final class Galois {

    /**
     * The number of elements in the field.
     */

    private static final int FIELD_SIZE = 256;

    /**
     * The polynomial used to generate the logarithm table.
     * 用来生成对数表的多项式
     * <p>
     * There are a number of polynomials that work to generate
     * a Galois field of 256 elements.  The choice is arbitrary,
     * and we just use the first one.
     * 用于生成 伽罗华域256个元素 的多项式有多个，使用任何一个是随意的，这里选择了第一个
     * <p>
     * The possibilities are: 29, 43, 45, 77, 95, 99, 101, 105,
     * 113, 135, 141, 169, 195, 207, 231, and 245.
     */

    static final int GENERATING_POLYNOMIAL = 29;

    /**
     * Mapping from members of the Galois Field to their
     * integer logarithms.  The entry for 0 is meaningless
     * because there is no log of 0.
     * 伽罗华域对应的的整数对数表，忽略0(无意义)
     * <p>
     * LOG_TABLE[x] = （log x mod 256）^ polynomial
     * 2 为底
     * <p>
     * This array is shorts, not bytes, so that they can
     * be used directly to index arrays without casting.
     * The values (except the non-value at index 0) are
     * all really bytes, so they range from 0 to 255.
     * 这个数组是short，而不是bytes，所以它们可以直接用于索引数组，无需强制转换
     * <p>
     * <p>
     * This table was generated by java_tables.py, and the
     * unit tests check it against the Java implementation.
     */

    static final short[] LOG_TABLE = new short[]{
            -1, 0, 1, 25, 2, 50, 26, 198,
            3, 223, 51, 238, 27, 104, 199, 75,
            4, 100, 224, 14, 52, 141, 239, 129,
            28, 193, 105, 248, 200, 8, 76, 113,
            5, 138, 101, 47, 225, 36, 15, 33,
            53, 147, 142, 218, 240, 18, 130, 69,
            29, 181, 194, 125, 106, 39, 249, 185,
            201, 154, 9, 120, 77, 228, 114, 166,
            6, 191, 139, 98, 102, 221, 48, 253,
            226, 152, 37, 179, 16, 145, 34, 136,
            54, 208, 148, 206, 143, 150, 219, 189,
            241, 210, 19, 92, 131, 56, 70, 64,
            30, 66, 182, 163, 195, 72, 126, 110,
            107, 58, 40, 84, 250, 133, 186, 61,
            202, 94, 155, 159, 10, 21, 121, 43,
            78, 212, 229, 172, 115, 243, 167, 87,
            7, 112, 192, 247, 140, 128, 99, 13,
            103, 74, 222, 237, 49, 197, 254, 24,
            227, 165, 153, 119, 38, 184, 180, 124,
            17, 68, 146, 217, 35, 32, 137, 46,
            55, 63, 209, 91, 149, 188, 207, 205,
            144, 135, 151, 178, 220, 252, 190, 97,
            242, 86, 211, 171, 20, 42, 93, 158,
            132, 60, 57, 83, 71, 109, 65, 162,
            31, 45, 67, 216, 183, 123, 164, 118,
            196, 23, 73, 236, 127, 12, 111, 246,
            108, 161, 59, 82, 41, 157, 85, 170,
            251, 96, 134, 177, 187, 204, 62, 90,
            203, 89, 95, 176, 156, 169, 160, 81,
            11, 245, 22, 235, 122, 117, 44, 215,
            79, 174, 213, 233, 230, 231, 173, 232,
            116, 214, 244, 234, 168, 80, 88, 175

    };

    /**
     * Inverse of the logarithm table.  Maps integer logarithms
     * to members of the field.  There is no entry for 255
     * because the highest log is 254.
     * 对数表的逆，整数对数对应的伽罗华域
     *
     * <p>
     * This table was generated by java_tables.py.
     */

    static final byte[] EXP_TABLE = new byte[]{
            1, 2, 4, 8, 16, 32, 64, -128,
            29, 58, 116, -24, -51, -121, 19, 38,
            76, -104, 45, 90, -76, 117, -22, -55,
            -113, 3, 6, 12, 24, 48, 96, -64,
            -99, 39, 78, -100, 37, 74, -108, 53,
            106, -44, -75, 119, -18, -63, -97, 35,
            70, -116, 5, 10, 20, 40, 80, -96,
            93, -70, 105, -46, -71, 111, -34, -95,
            95, -66, 97, -62, -103, 47, 94, -68,
            101, -54, -119, 15, 30, 60, 120, -16,
            -3, -25, -45, -69, 107, -42, -79, 127,
            -2, -31, -33, -93, 91, -74, 113, -30,
            -39, -81, 67, -122, 17, 34, 68, -120,
            13, 26, 52, 104, -48, -67, 103, -50,
            -127, 31, 62, 124, -8, -19, -57, -109,
            59, 118, -20, -59, -105, 51, 102, -52,
            -123, 23, 46, 92, -72, 109, -38, -87,
            79, -98, 33, 66, -124, 21, 42, 84,
            -88, 77, -102, 41, 82, -92, 85, -86,
            73, -110, 57, 114, -28, -43, -73, 115,
            -26, -47, -65, 99, -58, -111, 63, 126,
            -4, -27, -41, -77, 123, -10, -15, -1,
            -29, -37, -85, 75, -106, 49, 98, -60,
            -107, 55, 110, -36, -91, 87, -82, 65,
            -126, 25, 50, 100, -56, -115, 7, 14,
            28, 56, 112, -32, -35, -89, 83, -90,
            81, -94, 89, -78, 121, -14, -7, -17,
            -61, -101, 43, 86, -84, 69, -118, 9,
            18, 36, 72, -112, 61, 122, -12, -11,
            -9, -13, -5, -21, -53, -117, 11, 22,
            44, 88, -80, 125, -6, -23, -49, -125,
            27, 54, 108, -40, -83, 71, -114,
            // Repeat the table a second time, so multiply()
            // does not have to check bounds.
            1, 2, 4, 8, 16, 32, 64, -128,
            29, 58, 116, -24, -51, -121, 19, 38,
            76, -104, 45, 90, -76, 117, -22, -55,
            -113, 3, 6, 12, 24, 48, 96, -64,
            -99, 39, 78, -100, 37, 74, -108, 53,
            106, -44, -75, 119, -18, -63, -97, 35,
            70, -116, 5, 10, 20, 40, 80, -96,
            93, -70, 105, -46, -71, 111, -34, -95,
            95, -66, 97, -62, -103, 47, 94, -68,
            101, -54, -119, 15, 30, 60, 120, -16,
            -3, -25, -45, -69, 107, -42, -79, 127,
            -2, -31, -33, -93, 91, -74, 113, -30,
            -39, -81, 67, -122, 17, 34, 68, -120,
            13, 26, 52, 104, -48, -67, 103, -50,
            -127, 31, 62, 124, -8, -19, -57, -109,
            59, 118, -20, -59, -105, 51, 102, -52,
            -123, 23, 46, 92, -72, 109, -38, -87,
            79, -98, 33, 66, -124, 21, 42, 84,
            -88, 77, -102, 41, 82, -92, 85, -86,
            73, -110, 57, 114, -28, -43, -73, 115,
            -26, -47, -65, 99, -58, -111, 63, 126,
            -4, -27, -41, -77, 123, -10, -15, -1,
            -29, -37, -85, 75, -106, 49, 98, -60,
            -107, 55, 110, -36, -91, 87, -82, 65,
            -126, 25, 50, 100, -56, -115, 7, 14,
            28, 56, 112, -32, -35, -89, 83, -90,
            81, -94, 89, -78, 121, -14, -7, -17,
            -61, -101, 43, 86, -84, 69, -118, 9,
            18, 36, 72, -112, 61, 122, -12, -11,
            -9, -13, -5, -21, -53, -117, 11, 22,
            44, 88, -80, 125, -6, -23, -49, -125,
            27, 54, 108, -40, -83, 71, -114
    };

    /**
     * A multiplication table for the Galois field.
     * 伽罗华域 乘法表
     * <p>
     * Using this table is an alternative to using the multiply() method,
     * which uses log/exp table lookups.
     */
    static byte[][] MULTIPLICATION_TABLE = generateMultiplicationTable();

    /**
     * Adds two elements of the field.  If you're in an inner loop,
     * you should inline this function: it's just XOR.
     * 加法，异或运算
     */
    static byte add(byte a, byte b) {
        return (byte) (a ^ b);
    }

    /**
     * Inverse of addition.  If you're in an inner loop,
     * you should inline this function: it's just XOR.
     * 加法的逆运算，异或运算
     */
    static byte subtract(byte a, byte b) {
        return (byte) (a ^ b);
    }

    /**
     * Multiplies two elements of the field.
     * 乘法，查表
     */
    public static byte multiply(byte a, byte b) {
        if (a == 0 || b == 0) {
            return 0;
        } else {
            int logA = LOG_TABLE[a & 0xFF];
            int logB = LOG_TABLE[b & 0xFF];
            int logResult = logA + logB;
            return EXP_TABLE[logResult];
        }
    }

    /**
     * Inverse of multiplication.
     * 除法，查表
     */
    static byte divide(byte a, byte b) {
        if (a == 0) {
            return 0;
        }
        if (b == 0) {
            throw new IllegalArgumentException("Argument 'divisor' is 0");
        }
        int logA = LOG_TABLE[a & 0xFF];
        int logB = LOG_TABLE[b & 0xFF];
        int logResult = logA - logB;
        if (logResult < 0) {
            logResult += 255;
        }
        return EXP_TABLE[logResult];
    }

    /**
     * Computes a**n.
     * a 的 n 次幂，查表
     * <p>
     * The result will be the same as multiplying a times itself n times.
     *
     * @param a A member of the field.
     * @param n A plain-old integer.
     * @return The result of multiplying a by itself n times.
     */
    static byte exp(byte a, int n) {
        if (n == 0) {
            return 1;
        } else if (a == 0) {
            return 0;
        } else {
            int logA = LOG_TABLE[a & 0xFF];
            int logResult = logA * n;
            while (255 <= logResult) {
                logResult -= 255;
            }
            return EXP_TABLE[logResult];
        }
    }

    /**
     * Generates a logarithm table given a starting polynomial.
     * 生成一个给定起始多项式的对数表  定义域值域均为 [0,256] ，其中定义域 0无意义  设为 -1
     * 方式： short[index] = value，根据 value 确定 index ，[0,256]遍历一次
     * 0 放哪
     * 1 放哪
     * 2 放哪
     * 3 放哪
     * 。。。
     * <p>
     * LOG_TABLE
     */
    static short[] generateLogTable(int polynomial) {
        short[] result = new short[FIELD_SIZE];
        for (int i = 0; i < FIELD_SIZE; i++) {
            // -1 means "not set"
            result[i] = -1;
        }
        int b = 1;
        for (int log = 0; log < FIELD_SIZE - 1; log++) {
            // 位置b的值 始终应该是初始化值 -1，否则说明该 polynomial 不是本源多项式
            if (result[b] != -1) {
                throw new RuntimeException("BUG: duplicate logarithm (bad polynomial?)");
            }
            result[b] = (short) log;
            b = (b << 1);
            // 若 b 大于等于 256 ，(b mod 256 ) ^ polynomial
            if (FIELD_SIZE <= b) {
                b = ((b - FIELD_SIZE) ^ polynomial);
            }
        }
        return result;
    }

    /**
     * Generates the inverse log table.
     * 生成 逆 对数表
     * EXP_TABLE
     */
    static byte[] generateExpTable(short[] logTable) {
        final byte[] result = new byte[FIELD_SIZE * 2 - 2];
        for (int i = 1; i < FIELD_SIZE; i++) {
            int log = logTable[i];
            result[log] = (byte) i;
            result[log + FIELD_SIZE - 1] = (byte) i;
        }
        return result;
    }

    /**
     * Generates a multiplication table as an array of byte arrays.
     * 以字节数组数组的形式生成乘法表
     * <p>
     * To get the result of multiplying a and b:
     * <p>
     * MULTIPLICATION_TABLE[a][b]
     */
    static byte[][] generateMultiplicationTable() {
        byte[][] result = new byte[256][256];
        for (int a = 0; a < FIELD_SIZE; a++) {
            for (int b = 0; b < FIELD_SIZE; b++) {
                result[a][b] = multiply((byte) a, (byte) b);
            }
        }
        return result;
    }

    /**
     * Returns a list of all polynomials that can be used to generate
     * the field.
     * 获取 所有可用于生成伽罗华域的 多项式
     * <p>
     * This is never used in the code; it's just here for completeness.
     */
    static Integer[] allPossiblePolynomials() {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < FIELD_SIZE; i++) {
            try {
                generateLogTable(i);
                result.add(i);
            } catch (RuntimeException e) {
                // this one didn't work
            }
        }
        return result.toArray(new Integer[0]);
    }

}
